package com.example.leetcode.design;

import lombok.extern.slf4j.Slf4j;

import java.util.HashMap;
import java.util.Map;

class CacheNode {

    int key;
    int value;
    CacheNode pre;
    CacheNode next;

    public CacheNode() {
    }

    public CacheNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

/**
 * 其实LRU缓存的数据结构就是一个 双向链表 + 哈希表 的结合体
 * 就是一个 LinkedHashMap 的实现
 * 只不过在get元素的时候，需要同时刷新节点到链表头部
 */
@Slf4j
class LRUCache {

    Map<Integer, CacheNode> cache = new HashMap<>();
    int size;
    int capacity;
    CacheNode head;
    CacheNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new CacheNode();
        this.tail = new CacheNode();
        head.next = tail;
        tail.pre = head;
        this.size = 0;
    }

    public int get(int key) {
        CacheNode curNode = cache.get(key);
        if (curNode == null) {
            return -1;
        }
        // 将当前使用的节点移动到头部
        curNode.pre.next = curNode.next;
        curNode.next.pre = curNode.pre;
        curNode.next = head.next;
        curNode.pre = head;
        curNode.next.pre = curNode;
        curNode.pre.next = curNode;
        return curNode.value;
    }

    public void put(int key, int value) {
        CacheNode curNode;
        if (cache.get(key) == null) {
            // 创建一个新节点
            curNode = new CacheNode(key, value);
            // 新节点加入哈希表
            cache.put(key, curNode);
            size++;

            // 新节点加入链表头部
            curNode.next = head.next;
            curNode.pre = head;
            curNode.next.pre = curNode;
            curNode.pre.next = curNode;

            // 判断是否超过容量
            if (size > capacity) {
                CacheNode lastNode = tail.pre;
                // 从map中删除当前节点
                cache.remove(lastNode.key);
                // 从链表中删除当前节点
                lastNode.pre.next = tail;
                lastNode.next.pre = lastNode.pre;
                lastNode.pre = null;
                lastNode.next = null;
                size--;
            }

        } else {
            curNode = cache.get(key);
            // 调用一次get方法刷新链表
            get(key);
            // 更新节点值
            curNode.value = value;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
public class leetcode146 {
    public static void main(String[] args) {
//        test01();
        test02();
        System.out.println("end");
    }

    private static void test02() {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2, 1);
        lRUCache.put(1, 1);
        lRUCache.put(2, 3);
        lRUCache.put(4, 1);
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(2));
    }

    private static void test01() {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
        lRUCache.put(3, 5);
        System.out.println(lRUCache.get(3));
    }
}
